package com.algorithm;

import java.util.Arrays;
import java.util.List;

/**
 * @author: sun.hongliang
 * @create: 2019/08/15 14:12
 */
public class BinnerySearch {

    public static void main(String[] args) {
//        System.out.println(coinChange(new int[]{2}, 3));
//        System.out.println(integerBreak(10));
        System.out.println(wiggleMaxLength(new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8}));
    }

    public int search(int[] nums, int target) {
        int rep = searchRevesePoint(nums);
        if (rep == 0) {
            return binySearch(nums, 0, nums.length - 1, target);
        }
        if (nums[rep] <= target && nums[0] <= target) {
            return binySearch(nums, 0, rep, target);
        }

        if (nums[nums.length - 1] >= target) {
            return binySearch(nums, rep + 1, nums.length - 1, target);
        }
        return -1;
    }

    public static int maxProduct(int[] nums) {
        int n = nums.length;
        int[] max = new int[n + 1];
        int[] min = new int[n + 1];

        max[0] = 1;
        min[0] = 1;
        int res = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] > 0) {
                max[i] = Math.max(max[i - 1] * nums[i - 1], Math.max(max[i - 1], nums[i - 1]));
                min[i] = Math.min(min[i - 1] * nums[i - 1], Math.min(min[i - 1], nums[i - 1]));
            } else {
                min[i] = Math.min(max[i - 1] * nums[i - 1], nums[i - 1]);
                max[i] = Math.max(min[i - 1] * nums[i - 1], nums[i - 1]);
            }
            res = Math.max(res, Math.max(nums[i - 1], max[i]));
        }
        System.out.println(Arrays.toString(max));
        System.out.println(Arrays.toString(min));
        return res;
    }

    public static int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[] p = new int[prices.length];
        p[0] = 0;
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            p[i] = Math.max(p[i - 1] + prices[i] - prices[i - 1], prices[i] - prices[i - 1]);
            res = Math.max(p[i], res);
        }
        System.out.println(Arrays.toString(p));
        return res;
    }

    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int temp = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                int pre = i - coins[j];
                if (pre > 0) {
                    if (dp[pre] != 0) {
                        temp = Math.min(dp[pre] + 1, temp);
                    }
                } else if (pre == 0) {
                    temp = Math.min(dp[pre] + 1, temp);
                }
            }
            dp[i] = temp == Integer.MAX_VALUE ? 0 : temp;
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount] == 0 ? -1 : dp[amount];
    }

    public int binySearch(int[] nums, int start, int end, int target) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

    public static int integerBreak(int n) {
        if (n < 2) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[2] = 1;
        dp[1] = 1;
        for (int i = 3; i <= n; i++) {
            int temp = 0;
            for (int j = 1; j < i; j++) {
                temp = Math.max(temp, Math.max(dp[j], j) * (i - j));
            }
            dp[i] = temp;
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

    public static int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return 1;
        int[] dp = new int[len];
        dp[0] = 1;
        dp[1] = 2;
        int max = 1;
        for (int i = 2; i < len; i++) {
            if ((nums[i - 1] - nums[i - 2]) * (nums[i] - nums[i - 1]) < 0) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            max = Math.max(dp[i], max);
        }
        System.out.println(Arrays.toString(dp));
        return max;
    }

    public int searchRevesePoint(int[] nums) {
        int target = 0;
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return mid;
            } else {
                if (nums[mid] > nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return target;
    }

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        int result = chars[length - 1] == '0' ? 0 : 1;
        // 上一个值 也就是 i+1 也可以理解为 next
        int pre = 1;

        for (int i = length - 2; i >= 0; i--) {
            if (chars[i] == '0') {
                pre = result;
                result = 0;
                continue;
            }
            // 按照 dp[i]+dp[i+1]<=26 逻辑向前推
            if ((chars[i] - '0') * 10 + (chars[i + 1] - '0') <= 26) {
                int temp = result;
                result = result + pre;
                pre = temp;
            } else {
                pre = result;
            }
        }
        return result;
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        for (int i = n - 2; i >= 0; i--) {
            List<Integer> t = triangle.get(i);
            for (int j = 0; j < t.size(); j++) {
                List<Integer> list = triangle.get(i + 1);
                t.set(j, t.get(j) + Math.min(list.get(j), list.get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}
